package tree;

import commons.TreeNode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;

/**
 * leet-code(98) 验证二叉搜索树
 *
 * @author Ringo
 * @date 2021/8/28 20:56
 */
public class IsValidBST {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(2, new TreeNode(1, null, null), new TreeNode(3, null, null));
        System.out.println(create().isValidBST(root));
    }


    public static IsValidBST create() {
        return new IsValidBST();
    }

    public boolean isValidBST(TreeNode root) {
//        return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
        return validate(root);
    }


    /**
     * 递归
     */
    private boolean validate(TreeNode x, long min, long max) {
        if (x == null)
            return true;
        if (x.val <= min || x.val >= max)
            return false;
        boolean left = validate(x.left, min, x.val);
        boolean right = validate(x.right, x.val, max);
        return left && right;
    }

    /**
     * 中序遍历
     */
    private boolean validate(TreeNode x) {
        if (x == null)
            return true;

        TreeNode p = x;
        Deque<TreeNode> stack = new ArrayDeque<>();

        // 中序遍历序列的前一个值
        long before = Long.MIN_VALUE;

        while (p != null || !stack.isEmpty()) {
            if (p != null) {
                stack.push(p);
                p = p.left;
            } else {
                p = stack.pop();
                if (p.val <= before)
                    return false;
                before = p.val;
                p = p.right;
            }
        }
        return true;
    }

}
